
在学习本章前请确认你已经学习了 动态规划部分简介 

在具体讲何为 "背包 dp" 前，先来看如下的例题

\begin{NOTE}{例题 \href{https://www.luogu.org/problemnew/show/P2871}{手链 Charm Bracelet}}{}
本题题意可概括为——N 物体，放入容量为 M 的背包，要求使总价值最大。由于每个物体只有 2 种情况——取与不取，正如二进制中的 0 和 1——这类问题便被称为 “0-1 背包问题”。

\end{NOTE}


\subsection{0-1 背包}

例题中已知条件有第 i 个物体的体积 v[i] 和价值 w[i], 背包总容量

显而易见的是，可以计算总价值的，只有已经放入背包的物体，因此该题中对 "是否为最大值" 的判断是建立在 "已经放入背包之中" 的基础之上的

已知对于一个容量为 v1，可以放置第 1 到第 i 件物体的背包，其最大总价值很明显等于容量为 v1 的背包，放有第 1 到第 (i-1) 件物体时的最大值 (第 i 件物体不取时) 或者是容量为 v1-v[i]的背包，放有第 1 到第 (i-1) 件物体时的最大值 + w i 

由此可以得出状态转移方程

\begin{itemize}
\item dp[v1][i]=max(dp[v1][i-1],dp[v1-v\textbackslash{}[i\textbackslash{}]][i-1]+w[i])
\end{itemize}

有了这样的思路，就可以顺利地写出代码了

\begin{cppcode}
for (int i = 1; i <= v1; i++)
  for (int l = 0; l <= v1 - i; l++) dp[l + i] = max(dp[l] + w[i], dp[l + i]);
\end{cppcode}

按照正确的思路，写出了这样的核心代码，然后就可以提交......

错！

让我们再回头看一下代码，i 表示当前判断的是第 i 个物体，l 则穷举体积，可是注意一个地方——l 是从 0 到 v1-v[i]

这意味着什么呢？举个栗子，可能在体积为 (l) 处取物体 i 新的 dp 值存到体积为 (l+v[i]) 处, 而在体积为 (l+v[i]) 处，物体 i 再次被取

所以，当以 0\textasciitilde{}v1-v[i]的顺序穷举时，物体实际上可能被加入多遍，这显然与题意不符

因此为了避免多取，穷举顺序应为 v1-v[i]\textasciitilde{}0

因此实际核心代码为

\begin{cppcode}
for (int i = 1; i <= v1; i++)
  for (int l = v1 - i; l >= 0; l--) dp[l + i] = max(dp[l] + w[i], dp[l + i]);
\end{cppcode}

例题代码

\begin{cppcode}
#include <bits/stdc++.h>
using namespace std;
const int maxn = 13010;
int n, v, c[maxn], w[maxn], most[maxn];
int main() {
  cin >> n >> v;
  for (int i = 1; i <= n; i++) {
    cin >> c[i] >> w[i];
  }
  for (int i = 1; i <= n; i++)
    for (int l = v; l >= c[i]; l--) {
      if (most[l - c[i]] + w[i] > most[l]) most[l] = most[l - c[i]] + w[i];
    }
  cout << most[v];
  return 0;
}
\end{cppcode}

Ps. 事实上，由小到大穷举是另一种背包问题的解法，稍后会提到

\subsection{完全背包}

\subsection{多重背包}
